package q112_hasPathSum;

import CommonClass.Common.TreeNode;
public class Solution_1 {

    /**
     * 此题首先要判断root是不是空节点 因此不能直接利用该函数进行递归，需要设计递归函数
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        return dfs(root, targetSum - root.val);
    }

    /*
    首先根据题意，必须要是根节点到叶子节点的路径才能够去计算target，而不是截取一段路径
    所以终止条件要设计在叶子节点
    1 到叶子节点满足条件就直接返回true
    2 否则就是不满足条件的叶子节点返回false
    3 对左右子节点进行判断
    4 以上都不成立 则返回false
    这里用了一个count参数来反复的计算到达每一个节点剩余的值
    也可以使用一个sum变量依次记录值，但是相较于该方法相对麻烦，还需要将target传入
    所以这种方法更为简便
    还需要注意的是 到达一个节点意味着count是已经减去了该节点的值的状态
    而不是减去前一个值
     */
    private boolean dfs(TreeNode root, int count) {
        // 遇到满足条件的叶子节点直接返回true
        if (root.left == null && root.right == null && count == 0) {
            return true;
        }
        // 否则遇到叶子节点就是false
        if (root.left == null && root.right == null) {
            return false;
        }

        if (root.left != null) {
            if (dfs(root.left, count - root.left.val)) {
                return true;
            }
        }

        if (root.right != null) {
            if (dfs(root.right, count - root.right.val)) {
                return true;
            }
        }
        // 注意 这里还需要考虑最后的返回值 如果以上都没有找到 那就是false
        return false;
    }


}
